# 给定一个整数数组 arr ，返回 arr 的 最大湍流子数组的长度 。
#  如果比较符号在子数组中的每个相邻元素对之间翻转，则该子数组是 湍流子数组 。
#  更正式地来说，当 arr 的子数组 A[i], A[i+1], ..., A[j] 满足仅满足下列条件时，我们称其为湍流子数组：
#  若 i <= k < j ：
#  当 k 为奇数时， A[k] > A[k+1]，且
#  当 k 为偶数时，A[k] < A[k+1]；
#  或 若 i <= k < j ：
#  当 k 为偶数时，A[k] > A[k+1] ，且
#  当 k 为奇数时， A[k] < A[k+1]。
#
#  示例 1：
# 输入：arr = [9,4,2,10,7,8,8,1,9]
# 输出：5
# 解释：arr[1] > arr[2] < arr[3] > arr[4] < arr[5]
#
#  示例 2：
# 输入：arr = [4,8,12,16]
# 输出：2
#
#  示例 3：
# 输入：arr = [100]
# 输出：1
from typing import List


class Solution:
    def maxTurbulenceSize2(self, arr: List[int]) -> int:
        """
        解法二：滑动窗口(双指针)
        遍历一次输入数组，记录上一个位置数值的变化是增加还是减少，只要上一个位置数值的变化与当前不同，
        当前得到湍流子数组的长度就加 1。在遍历的过程中，记录所有的湍流子数组的长度的最大值。
        :param arr:
        :return:
        """
        arrLen = len(arr)
        if arrLen < 2:
            return arrLen
        left, right, res, preState = 0, 1, 1, False  # left ~ right 即为湍流子数组
        while right < arrLen:
            curState = arr[right - 1] < arr[right]  # 用于标识相邻元素是否是递增关系
            if curState == preState:  # 符号相等，说明不是湍流子数组，left指针移动到当前的前一位
                left = right - 1
            if arr[right] == arr[right - 1]:
                left = right
            right += 1
            res = max(res, right - left)
            preState = curState
        return res

    def maxTurbulenceSize1(self, arr: List[int]) -> int:
        """
        解法一:动态规划
        :param arr:
        :return:
        """
        size = len(arr)
        # incDp[i] 表示以 nums[i]为结尾是大于 nums[i - 1] 的最大湍流子数组的长度
        # decDp[i] 表示以 nums[i]为结尾是小于 nums[i - 1] 的最大湍流子数组的长度
        incDp, decDp = [1] + [0] * (size - 1), [1] + [0] * (size - 1)
        res = 1
        for i in range(1, size):
            if arr[i - 1] < arr[i]:
                incDp[i] = decDp[i - 1] + 1
                decDp[i] = 1
            if arr[i - 1] > arr[i]:
                decDp[i] = incDp[i - 1] + 1
                incDp[i] = 1
            if arr[i - 1] == arr[i]:
                incDp[i] = 1
                decDp[i] = 1
            res = max(incDp[i], decDp[i], res)
        return res

    def maxTurbulenceSize(self, arr: List[int]) -> int:
        return self.maxTurbulenceSize2(arr)


if __name__ == "__main__":
    arr = [9, 4, 2, 10, 7, 8, 8, 1, 9]
    print(Solution().maxTurbulenceSize(arr))
